import bisect
from typing import List


class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        size = len(nums)

        # 计算每个位置前（包含当前位置）的最长递增子序列
        stack = []
        prefix = []
        for i in range(size):
            if not stack or stack[-1] < nums[i]:
                stack.append(nums[i])
            else:
                j = bisect.bisect_left(stack, nums[i])
                if stack[j] > nums[i]:
                    stack[j] = nums[i]
            prefix.append(len(stack))

        # 计算每个位置后（包含当前位置）的最长递减子序列
        stack = []
        suffix = []
        for i in range(size - 1, -1, -1):
            if not stack or stack[-1] < nums[i]:
                stack.append(nums[i])
            else:
                j = bisect.bisect_left(stack, nums[i])
                if stack[j] > nums[i]:
                    stack[j] = nums[i]
            suffix.append(len(stack))
        suffix.reverse()

        # 计算最大值
        ans = 0
        for i in range(1, size - 1):
            if prefix[i] >= 2 and suffix[i] >= 2:
                ans = max(ans, prefix[i] + suffix[i] - 1)
        return size - ans


if __name__ == "__main__":
    print(Solution().minimumMountainRemovals([1, 3, 1]))  # 0
    print(Solution().minimumMountainRemovals([2, 1, 1, 5, 6, 2, 3, 1]))  # 3
    print(Solution().minimumMountainRemovals([4, 3, 2, 1, 1, 2, 3, 1]))  # 4
    print(Solution().minimumMountainRemovals([1, 2, 3, 4, 4, 3, 2, 1]))  # 1

    # 测试用例82/89
    print(Solution().minimumMountainRemovals([9, 8, 1, 7, 6, 5, 4, 3, 2, 1]))  # 2

    # 测试用例85/89
    print(Solution().minimumMountainRemovals([100, 92, 89, 77, 74, 66, 64, 66, 64]))  # 6
